This invention relates to telecommunication networks of the kind that comprise nodes and trunks (or links) for carrying communication traffic among the nodes. More particularly, this invention relates to methods for designing such networks; i.e., for determining the layout of the physical interconnections within the network, and for choosing the trunk types for implementing such interconnections. Still more particularly, this invention relates to optimization methods for achieving such interconnections at least cost.
Trunks for carrying telecommunications traffic may be classified according to capacity and according to cost per mile (for purchasing or leasing the trunks). Typically, the cost per mile is not proportional to the capacity, but instead increases much less than linearly as the capacity is increased. For example, Table 1 gives a typical set of leasing prices for trunks of four types. As a consequence of such cost structures, an economy of scale is often achieved by concentrating traffic to or from relatively many nodes into relatively few trunks, at least in specific portions of a network.
Some communication networks lend themselves to an access network model, in which such economies of scale may be substantial. With reference to FIG. 1, such a network consists of core nodes 10 occupying a central core 15, and a distribution of end nodes 20. Links 25 interconnect the nodes. Each link comprises one or more trunks. Each of the core nodes typically has switching capability, and the core nodes are highly interconnected.
The end nodes are connected to the core via access network 35. To achieve economies of scale, traffic from neighboring end nodes is advantageously multiplexed on to relatively high-capacity trunks 30 on its way to the core. Conversely, traffic destined for the end nodes is demultiplexed after leaving the core.
In effect, the core, as a whole, serves as a main switch for traffic between the end nodes. For example, traffic to be routed from end node A to end node B may go first from A to core node C, then across the core to core node D, and finally to end node B.
Every node that lies outside the core is referred to here as an end node, even if it is an intermediate point for traffic to or from multiple other end nodes.
As a general rule, the nodes 20 of an economically efficient access network are organized by the links into a tree-like structure, as shown in FIG. 2. (In the figure, the links are denoted by reference numeral 40.) Links in such a structure have various branching depths, such as 1, 2, 3, and 4 in the case of links 40.1, 40.2, 40.3, and 40.4 of the figure, respectively. It will be apparent from the figure that there is no unique way to define such a structure. Instead, the branching depth of the link that reaches any given end node, and the branch (or sub-branch, etc.) with which any given end node is associated, are matters of design choice. Additionally, it is a matter of design choice whether to add capacity to a link by multiplying trunks of the same type, or by substituting trunks of higher capacity.
The design choices will generally be directed toward minimizing the total cost of the access network, while accommodating the expected demand from each of the end nodes. To xe2x80x9caccommodate demandxe2x80x9d means to provide sufficient capacity to carry demand to or from the respective end nodes. For convenience, we will refer to this desideratum as accommodating demand from the end nodes. It should be understood, however, that the actual flow of data may be to the end nodes, from the end nodes, or bidirectional.
The cost of the access network will be determined by the lengths of the various trunks that are installed, by the number of trunks of a given type that are installed between a given pair of nodes, and by the cost structure. Thus, each design choice will have an impact on the total cost of the access network. When there are only a few nodes in the access network, it is tractable to examine the most reasonable design choices and to identify those that result in minimum cost. However, practical access networks often have many tens, hundreds, or even thousands of nodes. In such cases, it is generally necessary to use an automated procedure to find a network design having relatively low cost.
Trunks must be acquired (i.e., purchased or leasedxe2x80x94the term purchase will be used herein to denote any type of acquisition) in whole units. Therefore, the problem of finding the least-cost network design lends itself naturally to the methodologies of integer programming (IP). The integer program is defined by the cost function to be minimized, and by the constraints to which the minimization is subject. The designer typically specifies the locations of the end nodes (thus determining the lengths of the pertinent trunks), the available trunk types, the cost structure, and the demand from each node. Conventionally, the cost structure specifies a capacity and a cost per mile for trunks of each respective type.
Unfortunately, the IP problem is NP-hard. As those versed in the relevant airts will appreciate, this implies that there can be no assurance that the optimal design has been achieved, or even approached, within any specified computation time that is practical in a commercial sense. As a consequence, IP formulations are of limited value in designing access networks of significant size.
An alternative to IP is to formulate the problem according to the methodologies of linear programming (LP). In an LP formulation, it would be permissible to purchase fractional trunks. Thus, certain strictures imposed by the IP approach are relaxed. As a consequence, the computational problem (in an LP formulation) becomes tractable.
However, such an approach can lead to inutile solutions. That is, a rounding rule could be applied to the LP solutions, which are largely expressed in terms of fractional purchased trunks, to derive realizable solutions using integral trunks. Naive applications of LP fail to constrain the problem in such a way that the optimal unrounded solution remains economically efficient after rounding.
One earlier approach to the design of least-cost networks is described in F. S. Salman et al., xe2x80x9cApproximating the Single-Sink Edge Installation Problem in Network Design,xe2x80x9d Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 1997), pp. 619-628. In that approach, which is limited to Euclidean metric spaces, a procedure of constructing successively smaller grids is used to distinguish between nodes that are relatively distant and those that are relatively close together.
Those authors were able to provide a performance bound of O(log D) for their approach, where D represents the total demand. That is, the total cost of a network designed by the method of Salman et al. is guaranteed to lie within O(log D) of the optimal cost. (The meaning of xe2x80x9cO( . . . )xe2x80x9d is explained below.) A performance bound is useful for choosing between design methods on a worst-case basis. However, a performance bound that is too great gives little or no assurance that, in practice, the pertinent method will give commercially desirable results.
Another such approach is described in B. Awerbuch and Y. Azar, xe2x80x9cBuy-at-Bulk Network Design,xe2x80x9d in Proceedings of the 38th Annual Symposium on Foundations of Computer Science, Miami Beach, Fla., October 1997, pp. 542-547. In that approach, the authors applied a method, referred to as a tree metric embedding method, for approximating distances within the network by distances on a tree structure. Those authors provided a performance bound of O(log N)2, where N represents the number of nodes in the network.
Large total demands are often encountered in actual networks, and practical networks often include large numbers of nodes. Therefore, the performance bounds provided by the method of Salman et al. and by the method of Awerbuch et al. may, in practice, be relatively high. Therefore, what the art still lacks is an automatic method for designing access networks that provides utile solutions and is assured of approaching within some distance, independent of network size and total demand, of the design whose cost is optimal.
We have invented such a method. We have proven, with mathematical rigor, that the total cost of an access network designed by our method will lie within O(K3), and can even lie within O(K2) of the optimal cost, if the trunk costs satisfy certain conditions. These conditions are satisfied by many commercially available trunks.
The symbol K represents the total number of different trunk types. To xe2x80x9clie within O(K2)xe2x80x9d of a given value means to be no greater than the product of such value times a second-order polynomial in K. Similarly, to xe2x80x9clie within O(K3)xe2x80x9d means to be no greater than the given value times a third-order polynomial in K.
Central to our method is a transformed cost structure. This new cost structure has two components for trunks of each type. One component is a fixed overhead cost "sgr" of a specified number of dollars per mile. When any amount of trunk of a given type is purchased, this cost is incurred. The other component is a service charge xcexc. The service charge is expressed as a specified number of dollars, per mile, per unit of capacity.
Let the trunk types be indexed by the positive integer k, and let k=1, 2, . . . indicate increasing order of capacity. Then the overhead cost per mile of one unit of trunk of each of the respective types will typically increase with k. If it is also true that the service charge per unit length decreases with increasing k, and if a further condition to be described below is satisfied, then the total cost of the access network will lie within O(K3) of the optimal cost.
The further condition, simply stated, is that it is economically inefficient to invest in a trunk and then use less than half its capacity. More precisely, the condition is: (a) for the first trunk type (k=1), the service charge per unit length is more than one-half the overhead charge per unit length. (b) For all other trunk types, the cost dxcexc+"sgr" incurred per mile for routing demand d is cheaper on the next lower trunk type kxe2x88x921 whenever the demand d is so small that the service charge dxcexck for routing it on a type-k trunk is less than half the overhead charge "sgr"k on the type-k trunk. (In fact, the factor xe2x80x9cone-halfxe2x80x9d could be replaced in sub-conditions (a) and (b) by any positive fraction without changing the sufficiency of this condition.)
The total cost of the access network will lie within O(K2) of the optimal cost, if yet a further condition is also satisfied. Simply stated, this condition is that the trunk overhead costs increase geometrically. More precisely, this condition is satisfied if there is a positive constant c for which:
"sgr"1xe2x89xa6c"sgr"2; "sgr"1+"sgr"2xe2x89xa6c"sgr"3; . . . ; "sgr"1+"sgr"2+ . . . +"sgr"kxe2x88x921xe2x89xa6c"sgr"k.
We have observed that this condition is often satisfied by practical cost structures.
Our invention involves the use of LP techniques. Our way of characterizing capacity costs affects the operation of the linear program. Specifically, when a given trunk type is purchased to effectuate a given link, one unit of overhead cost is incurred, and then a continuous quantity of capacity in that trunk type is purchased. This treatment results in solutions that can be rounded to provide useful designs.
One reason why our approach is more realistic is that our xe2x80x9coverhead costxe2x80x9d builds into the linear program a penalty for routing miniscule demands on expensive (i.e., high-capacity) trunks. That is, if a given trunk is invested to carry any demand at all, no matter how small, an overhead cost must be sustained. This reflects the fact that in real life, if any demand is to be routed on a given link, the cost for purchasing at least one whole link must be incurred. (It should be noted that in the LP phase of the solution, we permit fractional overhead costs to be sustained. In a subsequent xe2x80x9croundingxe2x80x9d phase, fractionally invested trunks are consolidated into whole units.) Without such a penalty, the linear program would simply buy fractional amounts of one trunk type only, namely the trunk type having the least cost per unit capacity, and it would route demand from each end node to its closest core node.
Thus, in one aspect, our invention involves a method for designing an access network, comprising a collection of end nodes interconnected by links, for carrying communication traffic between the end nodes and a core. The method includes providing information descriptive of end node locations, the level of demand associated with each end node, available trunk types and their related capacities, and a cost structure. The cost structure includes a fixed overhead cost for each trunk type, and a service charge per unit distance for each trunk type.
The method further includes incorporating the provided information in a linear program to find an optimal-cost access network. The method further includes solving the linear program, thereby to obtain a provisional solution that defines the composition and usage of each link of the optimal-cost access network.
For each such link, the composition is defined by a fractional level of investment (incurring a like fraction of the corresponding overhead charge) in each pertinent trunk type. Below, we use the symbol x to denote these investment variables.
Each link will carry demand from one or more end nodes. On the link, one or more trunks of various types may each carry a certain fraction of the demand from a given end node. The usage is defined by the fraction of the demand from each pertinent end node that is routed through each pertinent trunk type. Below, we use the symbol y to denote these usage variables.
The method further includes rounding the provisional solution, thereby to provide a rounded solution. The rounding is carried out such that each trunk in which there is a fractional investment is either removed, or replaced by a trunk in which there is an integral investment.
In specific embodiments of the invention, rounding is carried out first on trunks of the highest-capacity type, and then on trunk types of successively lower capacity. (In this regard, we will refer, below, to trunks of successively lower xe2x80x9corder.xe2x80x9d) Within each order, the rounding takes place in three phases. Each trunk is considered to be directed toward the core.
In the first phase, referred to as xe2x80x9cbuying,xe2x80x9d groups of alternative trunks are identified. Each said group is reduced to a single trunk in accordance with a rule based on the service charge for sending one unit of demand over each of the alternative trunks to the core. (It should be noted that a single trunk is treated here as though it had unlimited capacity. Therefore, in actual implementations, such a trunk may be realized as a bundle of parallel trunks.)
In the second phase, referred to as xe2x80x9crerouting,xe2x80x9d the demand previously carried by each alternative trunk removed in the buying phase is rerouted on a trunk of the next lower order.
The third phase, referred to as xe2x80x9cshortcutting,xe2x80x9d relates to each junction of two trunks of a common type. Each such trunk pair is replaced by a single trunk of the common type.